还没有笔记
选中页面文字后点击「高亮」按钮添加
从现在开始，我们通常会省略$\mathbb{Z} / n \mathbb{Z}$元素周围的方括号$[\cdot]_{n}$，除非我们想比较整数$a$与它在$\mathbb{Z} / n \mathbb{Z}$中的同余类$[a]_{n}$，或者我们想将$a$视为$\mathbb{Z} / n \mathbb{Z}$的一个元素，对于可能不同的$n$，在这种情况下我们会强调写成$[a]_{n}$。请注意，$\mathbb{Z} / n \mathbb{Z}$有两种代数运算：加法和乘法。此外，对于整数$a, b$，
例如，$a \cdot[b]_{n}$是加法群$\mathbb{Z} / n \mathbb{Z}$中的“指数”记法：如果$a>0$，那么$a \cdot[b]_{n}=\underbrace{[b]_{n}+\cdots+[b]_{n}}_{a \text{ 次}}$。
我们首先给出一个方程$a x=b$在$\mathbb{Z} / n \mathbb{Z}$中何时有解的判别准则，或者等价地说，同余方程$a x \equiv b \bmod n$在整数中何时有解。首先，有以下观察：
设$n \in \mathbb{N}$，设$d \in \mathbb{N}$是$n$的约数。
(i) 如果$a \in \mathbb{Z}$，那么$d \mid a \Longleftrightarrow[a]_{n} \in\left\langle[d]_{n}\right\rangle$。
(ii) 如果$a, a^{\prime}$是整数使得$a \equiv a^{\prime} \bmod n$，那么$d|a \Longleftrightarrow d| a^{\prime}$。
(iii) 如果$a, a^{\prime} \in \mathbb{Z}$且$a \equiv a^{\prime} \bmod n$，那么$\operatorname{gcd}(a, n)=\operatorname{gcd}\left(a^{\prime}, n\right)$。
证明。(i) ⟹：如果$a=k d$，那么$[a]_{n}=[k d]_{n}=k \cdot[d]_{n}$，因此$[a]_{n} \in\left\langle[d]_{n}\right\rangle$。$\Longleftarrow$：如果$[a]_{n} \in\left\langle[d]_{n}\right\rangle$，那么$[a]_{n}=k \cdot[d]_{n}=[k d]_{n}$对于某个整数$k$，因此$a=k d+\ell n$对于整数$k, \ell$。由于$d \mid k d$且$d|n, d| a$。
(ii) 根据(i)，$d \mid a \Longleftrightarrow[a]_{n} \in\left\langle[d]_{n}\right\rangle \Longleftrightarrow\left[a^{\prime}\right]_{n} \in\left\langle[d]_{n}\right\rangle$（因为$\left.\left[a^{\prime}\right]_{n}=[a]_{n}\right) \Longleftrightarrow d \mid a^{\prime}$。
(iii) 根据(ii)，$e \in \mathbb{N}$整除$a$和$n \Longleftrightarrow e$整除$a^{\prime}$和$n$。因此，$a$和$n$的公约数集合与$a^{\prime}$和$n$的公约数集合相同。因此，$a$和$n$的最大公约数与$a^{\prime}$和$n$的最大公约数相同。
函数$f\left([a]_{n}\right)=\operatorname{gcd}(a, n)$是$\mathbb{Z} / n \mathbb{Z}$到$\{1, \ldots, n\}$的一个良定义函数。特别是，如果$a, a^{\prime} \in \mathbb{Z}$且$a \equiv a^{\prime} \bmod n$，那么$a$和$n$互素$\Longleftrightarrow a^{\prime}$和$n$互素，因此$[a]_{n}$和$n$互素的陈述是良定义的。
现在我们回到将$\mathbb{Z} / n \mathbb{Z}$的元素写成整数的约定，但有时会模糊整数与$\mathbb{Z} / n \mathbb{Z}$元素之间的区别。
给定$a, c \in \mathbb{Z} / n \mathbb{Z}$，存在$x \in \mathbb{Z} / n \mathbb{Z}$使得$ax =c \Longleftrightarrow c \in\langle d\rangle$，其中$d=\operatorname{gcd}(a, n)$。
证明。为了避免$\mathbb{Z}$的元素与$\mathbb{Z} / n \mathbb{Z}$的元素之间的混淆，让我们将方程重写为$[a]_{n}[x]_{n}=[c]_{n}$，并确定何时它有解$x \in \mathbb{Z}$。方程$[a]_{n}[x]_{n}=[c]_{n}$有解$x \in \mathbb{Z} \Longleftrightarrow$存在$x \in \mathbb{Z}$使得$a x \equiv c \bmod n$。但是$a x \equiv c \bmod n$有解$x \in \mathbb{Z} \Longleftrightarrow c$和$a x$相差$n$的倍数，即存在整数$y$使得$c=a x+n y$。我们已经看到，这个最后一个条件等价于：$d \mid c$。根据引理 1.4.1(i)，这个条件等价于：$[c]_{n} \in\left\langle[d]_{n}\right\rangle$。去掉$[\cdot]_{n}$记法，这等价于$c \in\langle d\rangle$。
给定$a \in \mathbb{Z} / n \mathbb{Z}$，存在$x \in \mathbb{Z} / n \mathbb{Z}$使得$ax =1$，即$a$是$(\mathbb{Z} / n \mathbb{Z}, \cdot)$的可逆元$\Longleftrightarrow \operatorname{gcd}(a, n)=1$，即$a$和$n$互素。
回想一下，$(\mathbb{Z} / n \mathbb{Z})^{*}$是二元结构$(\mathbb{Z} / n \mathbb{Z}, \cdot)$中可逆元的集合。特别是，$\left((\mathbb{Z} / n \mathbb{Z})^{*}, \cdot\right)$是阿贝尔群。上述推论的陈述是：
每当我们写$(\mathbb{Z} / n \mathbb{Z})^{*}$时，群运算被理解为乘法。注意$(\mathbb{Z} / n \mathbb{Z})^{*}$不是$\mathbb{Z} / n \mathbb{Z}$的子群（其中运算必然是$+$）。
(i) $(\mathbb{Z} / 6 \mathbb{Z})^{*}=\{1,5\}$。必然有$(\mathbb{Z} / 6 \mathbb{Z})^{*} \cong \mathbb{Z} / 2 \mathbb{Z}$，并且$5$的阶是$2$，即在$\mathbb{Z} / 6 \mathbb{Z}$中$5^{2}=1$。
(ii) $(\mathbb{Z} / 5 \mathbb{Z})^{*}=\{1,2,3,4\}$，因此$\#\left((\mathbb{Z} / 5 \mathbb{Z})^{*}\right)=4$。很容易看出$(\mathbb{Z} / 5 \mathbb{Z})^{*}$是循环的。事实上，$2^{2}=4,2^{3}=3$，并且$2^{4}=1$，因此$(\mathbb{Z} / 5 \mathbb{Z})^{*}=\langle 2\rangle$。
(iii) 另一方面，$(\mathbb{Z} / 8 \mathbb{Z})^{*}=\{1,3,5,7\}$，因此$\#((\mathbb{Z} / 8 \mathbb{Z}))^{*}=4$。但是$(\mathbb{Z} / 8 \mathbb{Z})^{*}$不是循环的，因为$3^{2}=5^{2}=7^{2}=1$。因此$(\mathbb{Z} / 8 \mathbb{Z})^{*}$的每个元素的阶是$1$或$2$。特别是，$(\mathbb{Z} / 8 \mathbb{Z})^{*}$中没有阶为$4$的元素，因此$(\mathbb{Z} / 8 \mathbb{Z})^{*}$不是循环的。
定义欧拉$\phi$-函数$\phi: \mathbb{N} \rightarrow \mathbb{N}$为：
因此$\phi(n)$是整数$a, 0 \leq a \leq n-1$中使得$\operatorname{gcd}(a, n)=1$的数量。
如果$p$是素数，$\phi(p)=p-1$。更一般地，如果$p$是素数且$k \in \mathbb{N}$，那么
证明。假设$p^{k}$是素数的幂，即$p$是素数且$k \in \mathbb{N}$，包括$k=1$的情况。那么整数$a$与$p^{k}$不是互素的$\Longleftrightarrow$它与$p$有公因子$\Longleftrightarrow p \mid k \Longleftrightarrow k$是$p$的倍数。现在在$0$到$p^{k}-1$之间有$p^{k} / p=p^{k-1}$个$p$的倍数。因此整数$a, 0 \leq a \leq p^{k}-1$中与$p^{k}$互素的数量是$\phi\left(p^{k}\right)=p^{k}-p^{k-1}=p^{k-1}(p-1)$。
一般来说，对于$n>1, 1 \leq \phi(n) \leq n-1$，并且很容易看出$\phi(n)=n-1 \Longleftrightarrow n$是素数。下面是$\phi$的最初几个值的表格：
| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $\phi(n)$ | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 | 10 | 4 |
我们很快将描述函数$\phi(n)$的更多性质。
我们回到描述$\mathbb{Z} / n \mathbb{Z}$所有子群的问题。以下定理给出了完整的描述。
设$n \in \mathbb{N}$。
(i) $\mathbb{Z} / n \mathbb{Z}$的每个子群都是循环的。
(ii) 如果$a \in \mathbb{Z} / n \mathbb{Z}$且$d=\operatorname{gcd}(a, n)$，那么$\langle a\rangle=\langle d\rangle$。
(iii) 如果$a \in \mathbb{Z} / n \mathbb{Z}$且$d=\operatorname{gcd}(a, n)$，$a$的阶是$n / d=n / \operatorname{gcd}(a, n)$。
(iv) $\mathbb{Z} / n \mathbb{Z}$的每个子群的阶整除$n$。
(v) 对于$n$的每个约数$d$，$\mathbb{Z} / n \mathbb{Z}$中恰好有一个阶为$d$的子群，即$\langle n / d\rangle$。
证明。(i) 我们已经看到这一点。
(ii) 由于$d \mid a, a \in\langle d\rangle$，因此$\langle a\rangle \subseteq\langle d\rangle$。反之，根据命题 1.4.3，由于$d \mid d$，存在$x$使得$a x=d$，因此$x \cdot a=d$，从而$d \in\langle a\rangle$。因此$\langle d\rangle \subseteq\langle a\rangle$。由此可见$\langle a\rangle=\langle d\rangle$。
(iii) 根据(ii)，$\langle a\rangle=\langle d\rangle$，因此$a$的阶，我们知道它等于$\#(\langle a\rangle)$，等于$\#(\langle d\rangle)$，因此等于$d$的阶。显然$(n / d) \cdot d=n=0$在$\mathbb{Z} / n \mathbb{Z}$中，因此$d$的阶至多是$n / d$。另一方面，如果$0<k<n / d$，那么，将$d$视为整数，$0<k \cdot d<n$，因此在$\mathbb{Z} / n \mathbb{Z}$中$k \cdot d \neq 0$。因此$n / d$是使得$k \cdot d=0$的最小正整数$k$。所以$d$的阶，从而$a$的阶是$n / d$。
(iv) 如果$H \leq \mathbb{Z} / n \mathbb{Z}$，那么$H=\langle a\rangle$对于某个$a$，并且$H$的阶就是$a$的阶，即$n / d$对于$n$的某个约数$d$。但显然$n / d$整除$n$。
(v) 根据(i)和(ii)，$\mathbb{Z} / n \mathbb{Z}$的每个子群$H$都形如$\langle e\rangle$对于$n$的某个约数$e$。根据(iii)，$H$的阶是$n / e$。因此$\mathbb{Z} / n \mathbb{Z}$中阶为$d$的唯一子群是$\langle e\rangle$，其中$n / e=d$，即$e=n / d$。
$\langle a\rangle=\mathbb{Z} / n \mathbb{Z}$，即$a$是$\mathbb{Z} / n \mathbb{Z}$的生成元$\Longleftrightarrow \operatorname{gcd}(a, n)=1 \Longleftrightarrow a \in(\mathbb{Z} / n \mathbb{Z})^{*}$。
证明。$\langle a\rangle=\mathbb{Z} / n \mathbb{Z} \Longleftrightarrow a$的阶是$n \Longleftrightarrow$对于$d=\operatorname{gcd}(a, n), n / d=n \Longleftrightarrow d=1$。
给定$a \in(\mathbb{Z} / n \mathbb{Z})^{*}$，请注意不要混淆$a$作为$\mathbb{Z} / n \mathbb{Z}$元素的阶与$a$作为$(\mathbb{Z} / n \mathbb{Z})^{*}$元素的阶。作为$\mathbb{Z} / n \mathbb{Z}$的元素，$a$的阶总是$n$根据上述推论。但作为$(\mathbb{Z} / n \mathbb{Z})^{*}$的元素，$a$的阶可以是$1$（如果$a=1$），并且通常至多是$\phi(n)$。
上述所有内容都可以转换到更一般的有限循环群的上下文中。
设$G$是一个阶为$n$的有限循环群，设$g$是$G$的一个生成元。那么：
(i) $G$的每个子群都是循环的，并且$G$的每个子群的阶整除$n$。
(ii) 如果$a \in \mathbb{Z}$且$d=\operatorname{gcd}(a, n)$，那么$\left\langle g^{a}\right\rangle=\left\langle g^{d}\right\rangle$。此外，$g^{a}$的阶是$n / d$。特别是，$g^{a}$是$G$的生成元$\Longleftrightarrow \operatorname{gcd}(a, n)=1$。
(iii) 对于$n$的每个约数$d$，$G$中恰好有一个阶为$d$的子群，即$\left\langle g^{n / d}\right\rangle$。
(iv) $G$的生成元的数量是$\phi(n)$。
证明。只需对$G=\mathbb{Z} / n \mathbb{Z}$进行验证，这由我们之前的结果得出。
群$\mu_{n}$是循环的；事实上，$\mu_{n}=\left\langle e^{2 \pi i / n}\right\rangle$。单位的$n$次根$z$是本原的$n$次单位根，如果$z^{n}=1$但没有更小的$z$的幂等于$1$，即$z$在群$\mu_{n}$中的阶是$n$。这仅仅是说$z$是$\mu_{n}$的生成元，因此根据(ii)，这等价于$z=e^{2 a \pi i / n}$，其中$\operatorname{gcd}(a, n)=1$。
考虑群$(\mathbb{Z} / 7 \mathbb{Z})^{*}$，阶为$6$。注意$2^{2}=4$且$2^{3}=1$。因此$2$的阶是$3$，不是$(\mathbb{Z} / 7 \mathbb{Z})^{*}$的生成元。但是$3^{2}=2,3^{3}=6=-1$，因此$3^{6}=(-1)^{2}=1$。根据一般结果，这表明$3$的阶必须整除$6$。正如我们所见，阶不是$2$或$3$，因此$3$的阶是$6$，并且$(\mathbb{Z} / 7 \mathbb{Z})^{*}=\langle 3\rangle$恰好是循环的。
上述推论表明$(\mathbb{Z} / 7 \mathbb{Z})^{*}$恰好有一个阶为$1,2,3,6$的子群，并且这些是所有子群。事实上，它告诉我们如何找到它们：阶为$1$的子群是$\left\langle 3^{6}\right\rangle=\langle 1\rangle$，阶为$2$的子群是$\left\langle 3^{3}\right\rangle=\langle 6\rangle=\langle-1\rangle$，阶为$3$的子群是
$\left\langle 3^{2}\right\rangle=\langle 2\rangle$，阶为$6$的子群是$\langle 3\rangle$。此外，$(\mathbb{Z} / 7 \mathbb{Z})^{*}$的生成元恰好是$3^{a}$，其中$a$取模$6$且$\operatorname{gcd}(a, 6)=1$。$a$的唯一可能性是$1$和$5$，因此$(\mathbb{Z} / 7 \mathbb{Z})^{*}$的生成元是$3^{1}=3$和$3^{5}=3^{-1}=5$。
对于每个$d \mid n$，$\mathbb{Z} / n \mathbb{Z}$中恰好有$\phi(d)$个阶为$d$的元素。
证明。给定$a \in \mathbb{Z} / n \mathbb{Z}$，$a$的阶是$d \Longleftrightarrow \#(\langle a\rangle)=d \Longleftrightarrow\langle a\rangle=\langle n / d\rangle \Longleftrightarrow a \in\langle n / d\rangle$并且$a$是$\langle n / d\rangle$的生成元。由于$\langle n / d\rangle$是一个阶为$d$的循环群，根据前面的推论，它恰好有$\phi(d)$个生成元。因此$\mathbb{Z} / n \mathbb{Z}$中恰好有$\phi(d)$个阶为$d$的元素$a$。
事实上，给定$d \mid n$，$\mathbb{Z} / n \mathbb{Z}$中阶为$d$的$\phi(d)$个元素的集合与集合
是等同的。
对于每个自然数$n$，
证明。根据定理的(iii)，$\mathbb{Z} / n \mathbb{Z}$的每个元素都有一个整除$n$的阶$d$。根据推论 1.4.13，对于每个$d \mid n$，$\mathbb{Z} / n \mathbb{Z}$中恰好有$\phi(d)$个阶为$d$的元素。因此和式$\sum_{d \mid n} \phi(d)$计算的是$\mathbb{Z} / n \mathbb{Z}$的元素数量，即$n$。
例如，20的约数是$1,2,4,5,10$和$20$。我们有
如果$G$是有限循环群，那么$G$的每个子群的阶整除$G$的阶。事实上，正如我们将看到的，这对于每个有限群都成立，被称为拉格朗日定理：如果$G$是有限群且$H \leq G$，那么$\#(H) \mid \#(G)$。然而，$\mathbb{Z} / n \mathbb{Z}$对于$n=\#(\mathbb{Z} / n \mathbb{Z})$的每个约数$d$恰好有一个阶为$d$的子群，这是$\mathbb{Z} / n \mathbb{Z}$（或更一般的有限循环群）的一个非常特殊的性质。对于一般的有限群$G$和$\#(G)$的约数$d$，可能没有阶为$d$的子群，或者有几个（例如在$(\mathbb{Z} / 2 \mathbb{Z}) \times(\mathbb{Z} / 2 \mathbb{Z}), D_{3}$或$Q$的情况下）。
设$n, m \in \mathbb{N}$且$\operatorname{gcd}(n, m)=1$。那么
等价地，$(\mathbb{Z} / n \mathbb{Z}) \times(\mathbb{Z} / m \mathbb{Z})$是循环的。
一个等价的表述如下：
设$n, m \in \mathbb{N}$且$\operatorname{gcd}(n, m)=1$。那么，对于所有的$r, s \in \mathbb{Z}$，存在一个$x \in \mathbb{Z}$使得
此外，如果$x$和$x^{\prime}$满足上述同余式，那么$x \equiv x^{\prime} \bmod n m$。
以这种形式，该结果在公元300-500年间已知（在中国以及后来的印度和西方）。
为了证明中国剩余定理，我们首先从以下关于群的一般引理开始，这留作练习（练习 3.7）：
设$G_{1}$和$G_{2}$是群，设$g_{1} \in G_{1}$和$g_{2} \in G_{2}$。假设$g_{1}$具有有限阶$d_{1}$且$g_{2}$具有有限阶$d_{2}$。那么群$G_{1} \times G_{2}$中$\left(g_{1}, g_{2}\right)$的阶是$d_{1}$和$d_{2}$的最小公倍数。
中国剩余定理的证明。将引理应用于元素$(1,1) \in (\mathbb{Z} / n \mathbb{Z}) \times(\mathbb{Z} / m \mathbb{Z})$，我们看到$(1,1)$的阶是$n$和$m$的最小公倍数。一个通用公式（练习 3.6）表明，$n$和$m$的最小公倍数等于$n m / \operatorname{gcd}(n, m)$，因此如果$\operatorname{gcd}(n, m)=1$，则为$n m$。（事实上，在$\operatorname{gcd}(n, m)=1$的情况下，很容易直接验证这一点。）因此，在$\operatorname{gcd}(n, m)=1$的假设下，$(\mathbb{Z} / n \mathbb{Z}) \times(\mathbb{Z} / m \mathbb{Z})$具有阶为$n m$的元素，这是$(\mathbb{Z} / n \mathbb{Z}) \times(\mathbb{Z} / m \mathbb{Z})$的阶。因此$(\mathbb{Z} / n \mathbb{Z}) \times(\mathbb{Z} / m \mathbb{Z})$是循环的，事实上它由$(1,1)$生成。
上述证明方法计算了$(\mathbb{Z} / n \mathbb{Z}) \times (\mathbb{Z} / m \mathbb{Z})$的每个元素的阶，无论$n$和$m$是否互素。如果$\operatorname{gcd}(n, m)>1$，那么类似于上述证明的论证表明$(\mathbb{Z} / n \mathbb{Z}) \times (\mathbb{Z} / m \mathbb{Z})$的每个元素的阶都整除$n$和$m$的最小公倍数，即$n m / \operatorname{gcd}(n, m)$，因此严格小于$n m$。因此$(\mathbb{Z} / n \mathbb{Z}) \times (\mathbb{Z} / m \mathbb{Z})$中没有阶为$n m$的元素，因此$(\mathbb{Z} / n \mathbb{Z}) \times (\mathbb{Z} / m \mathbb{Z})$不是循环的。例如，我们已经看到$(\mathbb{Z} / 2 \mathbb{Z}) \times (\mathbb{Z} / 2 \mathbb{Z})$中的每个元素的阶是$1$或$2$。
为了理解我们上面证明的中国剩余定理版本与版本2之间的联系，仍然在$\operatorname{gcd}(n, m)=1$的假设下，回想一下，由于元素$(1,1) \in (\mathbb{Z} / n \mathbb{Z}) \times(\mathbb{Z} / m \mathbb{Z})$具有阶$n m$，存在一个显式同构$f: \mathbb{Z} / n m \mathbb{Z} \rightarrow(\mathbb{Z} / n \mathbb{Z}) \times(\mathbb{Z} / m \mathbb{Z})$，由$f(a)=(a, a)$给出。更准确地说，为了跟踪我们正在使用的群，我们可以写成
（回想练习 1.19，函数$g_{1}: \mathbb{Z} / n m \mathbb{Z} \rightarrow \mathbb{Z} / n \mathbb{Z}$定义为$g_{1}\left([a]_{n m}\right)=[a]_{n}$是良定义的，因为$n \mid n m$，对于函数$g_{2}: \mathbb{Z} / n m \mathbb{Z} \rightarrow \mathbb{Z} / m \mathbb{Z}$定义为$g_{2}\left([a]_{n m}\right)= [a]_{m}$也类似。）由于$f$是同构，它也是双射。因此，对于每个$[r]_{n} \in \mathbb{Z} / n \mathbb{Z}$和$[s]_{m} \in \mathbb{Z} / m \mathbb{Z}$，存在一个唯一的$[x]_{n m} \in \mathbb{Z} / n m \mathbb{Z}$使得$f\left([x]_{n m}\right)=\left([r]_{n},[s]_{m}\right)$。这本质上是中国剩余定理的版本2。
(1) 还有中国剩余定理版本2的证明，它给出了$x$的显式推导方法。
(2) 在$n$和$m$不一定互素的情况下，很容易给出同余式
有解的必要条件和充分条件。
我们现在转向中国剩余定理的乘法形式。
假设$\operatorname{gcd}(n, m)=1$，设$g$表示同构$f: \mathbb{Z} / n m \mathbb{Z} \rightarrow(\mathbb{Z} / n \mathbb{Z}) \times(\mathbb{Z} / m \mathbb{Z})$对$(\mathbb{Z} / n m \mathbb{Z})^{*}$的限制，即$g=f \mid(\mathbb{Z} / n m \mathbb{Z})^{*}$。
(i) $g$的像是$(\mathbb{Z} / n \mathbb{Z})^{*} \times(\mathbb{Z} / m \mathbb{Z})^{*}$。
(ii) 如果我们用$f^{*}$表示由此产生的双射$(\mathbb{Z} / n m \mathbb{Z})^{*} \rightarrow(\mathbb{Z} / n \mathbb{Z})^{*} \times(\mathbb{Z} / m \mathbb{Z})^{*}$，那么$f^{*}$是同构。因此，特别是
证明。(i) 这源于这样一个事实：给定$a \in \mathbb{Z}$，
这是练习 3.5。因此，如果$[a]_{n m} \in(\mathbb{Z} / n m \mathbb{Z})^{*}，g\left([a]_{n m}\right)=f\left([a]_{n m}\right)=\left([a]_{n},[a]_{m}\right) \in(\mathbb{Z} / n \mathbb{Z})^{*} \times (\mathbb{Z} / m \mathbb{Z})^{*}$。因此$g$的像包含在$(\mathbb{Z} / n \mathbb{Z})^{*} \times (\mathbb{Z} / m \mathbb{Z})^{*}$中，并且$g$是单射因为$f$是单射。为了看出$g$的像恰好是$(\mathbb{Z} / n \mathbb{Z})^{*} \times (\mathbb{Z} / m \mathbb{Z})^{*}$，设$\left([r]_{n},[s]_{m}\right) \in(\mathbb{Z} / n \mathbb{Z})^{*} \times (\mathbb{Z} / m \mathbb{Z})^{*}$。那么，由于$f$是满射，存在一个$[a]_{n m} \in \mathbb{Z} / n m \mathbb{Z}$使得$f\left([a]_{n m}\right)=\left([a]_{n},[a]_{m}\right)= \left([r]_{n},[s]_{m}\right)$。那么$\operatorname{gcd}(a, n)=\operatorname{gcd}(r, n)=1$，同样$\operatorname{gcd}(a, m)=\operatorname{gcd}(s, m)=1$。根据练习 3.5可知$a \in(\mathbb{Z} / n m \mathbb{Z})^{*}$。因此$g$的像是$(\mathbb{Z} / n \mathbb{Z})^{*} \times (\mathbb{Z} / m \mathbb{Z})^{*}$，并且$g$定义了一个双射
为了看出$f^{*}$是同构，我们计算：
因此$f^{*}\left([a]_{n m}[b]_{n m}\right)=f^{*}\left([a]_{n m}\right) f^{*}\left([b]_{n m}\right)$，所以$f^{*}$是同构。
我们得到以下推论：
如果$\operatorname{gcd}(n, m)=1$，那么$\phi(n m)=\phi(n) \phi(m)$。
这导致了$\phi(n)$的以下“显式”公式：
假设$n=p_{1}^{a_{1}} \cdots p_{r}^{a_{r}}$是$n$的素因数分解，其中$p_{1}, \ldots, p_{r}$是不同的素数且$a_{i} \geq 1$。那么
（有时这写成$\varphi(n)=n \prod_{p \mid n}\left(1-\frac{1}{p}\right)$，其中乘积取自所有整除$n$的素数。）
稍后我们将讨论（但仅在第二部分证明）：
如果$p$是素数，那么$(\mathbb{Z} / p \mathbb{Z})^{*}$是循环的，因此同构于$\mathbb{Z} /(p-1) \mathbb{Z}$。
这里，循环群$(\mathbb{Z} / p \mathbb{Z})^{*}$的生成元称为原根。找到这样的生成元本质上是试错法。但是，我们可以使用以下内容：
设$G$是阶为$n$的有限群，不一定假设为阿贝尔群。假设$g \in G$是一个元素，使得$g^{n}=1$，但对于每个$d \in \mathbb{N}$，使得$d \mid n$但$d \neq n, g^{d} \neq 1$。那么$g$的阶是$n$并且$G=\langle g\rangle$，因此$G$是循环的且$g$是生成元。
证明。由于$g^{n}=1$，根据推论 1.1.3，$g$的阶是$n$的约数。但由于对于$n$的每个真约数$d, g^{d} \neq 1$，因此对于所有$k<n, g^{k} \neq 1$，因此$g$的阶是$n$。那么$G=\langle g\rangle$，因为$\langle g\rangle \subseteq G$并且两个集合都有$n$个元素。
群$(\mathbb{Z} / 25 \mathbb{Z})^{*}$的阶是$\phi(25)=4 \cdot 5=20$。取$2$的幂次，$2^{2}=4$, $2^{3}=8$, $2^{4}=16$, $2^{5}=32=7$, $2^{10}=49=24=-1$，因此$2^{20}=\left(2^{10}\right)^{2}=(-1)^{2}=1$。这表明$2$的阶整除$20$，但不等于$1,2,4,5,10$。因此$2$的阶是$20$，并且$(\mathbb{Z} / 25 \mathbb{Z})^{*} \cong \mathbb{Z} / 20 \mathbb{Z}$。
原则上，我们可以回答所有关于$(\mathbb{Z} / 25 \mathbb{Z})^{*}$的问题。例如，$(\mathbb{Z} / 25 \mathbb{Z})^{*}$中阶为$20$的元素，即$(\mathbb{Z} / 25 \mathbb{Z})^{*}$的生成元，恰好是形如$2^{a}$的元素，其中$\operatorname{gcd}(a, 20)=1$，共有$\phi(20)=8$个。因此，$(\mathbb{Z} / 25 \mathbb{Z})^{*}$的生成元集合是
有一个唯一的阶为$10$的子群，即$\left\langle 2^{20 / 10}\right\rangle=\left\langle 2^{2}\right\rangle=\langle 4\rangle$。此外，每个阶为$10$的元素都形如$2^{2 a}=4^{a}$，其中$\operatorname{gcd}(a, 10)=1$，共有$4$个：$a=1,3,7,9$。对于阶为$1,2,4,5$的子群和元素也有类似的描述。
利用定理 1.5.9，可以证明：
(i) 如果$p$是奇素数，那么
因此，由于$\operatorname{gcd}\left(p-1, p^{k-1}\right)=1，\left(\mathbb{Z} / p^{k} \mathbb{Z}\right)^{*} \cong \mathbb{Z} /(p-1) p^{k-1} \mathbb{Z}$，特别是它是循环的。
(ii) 对于素数$2，(\mathbb{Z} / 2 \mathbb{Z})^{*}=\{1\}，(\mathbb{Z} / 4 \mathbb{Z})^{*} \cong \mathbb{Z} / 2 \mathbb{Z}$，如果$k \geq 3$，那么
注意素数$2$的特殊性在于，当$k \geq 3$时，$\left(\mathbb{Z} / 2^{k} \mathbb{Z}\right)^{*}$不是循环的。
群$(\mathbb{Z} / n \mathbb{Z})^{*}$是循环的$\Longleftrightarrow n$满足以下条件之一：
(1) $n=p^{k}$是素数的幂，其中$p$是奇素数。
(2) $n=2 p^{k}$，其中$p$是奇素数。
(3) $n=2$或$4$。
我们看到$(\mathbb{Z} / n \mathbb{Z})^{*}$很少是循环群。然而，命题 1.5.6和归纳法表明，如果$n$的素因数分解是$p_{1}^{a_{1}} \cdots p_{r}^{a_{r}}$如上所述，那么
因此，根据定理 1.5.12，$(\mathbb{Z} / n \mathbb{Z})^{*}$仍然是循环群的乘积。这里需要特别注意形如$\left(\mathbb{Z} / 2^{a} \mathbb{Z}\right)^{*}$的因子；从上面可以看出，$\left(\mathbb{Z} / 2^{a} \mathbb{Z}\right)^{*} \cong(\mathbb{Z} / 2 \mathbb{Z}) \times\left(\mathbb{Z} / 2^{a-2} \mathbb{Z}\right)$，当$a>2$时它不是循环的，但仍然是循环群的乘积。
上述是一个更一般结果的特例：
每个有限阿贝尔群都同构于循环群的乘积。
定理中也包含一个唯一性陈述，它有点复杂，但大致意思是，阿贝尔群表示为循环群的乘积的唯一性失败是由于中国剩余定理造成的，它意味着，对于$\operatorname{gcd}(n, m)=1$，我们可以将一对因子$(\mathbb{Z} / n \mathbb{Z}) \times(\mathbb{Z} / m \mathbb{Z})$替换为$\mathbb{Z} / n m \mathbb{Z}$。
原则上，有限阿贝尔群基本定理可以告诉我们关于有限阿贝尔群的所有信息，一旦我们将其描述为笛卡尔积$\left(\mathbb{Z} / n_{1} \mathbb{Z}\right) \times \cdots \times\left(\mathbb{Z} / n_{r} \mathbb{Z}\right)$的同构，并且我们知道正整数$n_{i}$。例如，原则上可以列出给定阶的所有元素和所有子群。然而，这些计算在实践中可能很困难，更像是线性代数而不是有限群论。
回想一下，给定一个集合$X$，从$X$到其自身的所有双射的集合$S_{X}$（或者，更简洁地，特别是当$X$是有限的时，X的排列）在函数复合下是一个群。特别是，对于每个$n \in \mathbb{N}$，对称群$S_{n}$是集合$\{1, \ldots, n\}$的排列群，群运算等于函数复合。因此，$S_{n}$是一个有$n!$个元素的群，如果$n \geq 3$，它不是阿贝尔群。如果$X$是一个有限集，其元素数量为$\#(X)=n$，那么将$X$的元素标记为$x_{1}, \ldots, x_{n}$定义了一个从$S_{X}$到$S_{n}$的同构$F$。显式地，给定$f \in S_{X}$，对于每个$i, f\left(x_{i}\right)=x_{j}=x_{\sigma(i)}$对于某个$j$和一个唯一的元素$\sigma \in S_{n}$，我们定义$F(f)(i)=j$，即$F(f)=\sigma$。
我们将用希腊字母$\sigma, \tau, \rho, \ldots$来表示$S_{n}$的元素，我们将恒等函数记为$1$，我们只使用并置（或偶尔使用乘号$\cdot$）来表示复合（而不是符号$\circ$）。然而，请记住函数是从右到左作用的：因此$\sigma \tau(i)= \sigma(\tau(i))$，换句话说，先计算$\tau$在$i$处的值，然后计算$\sigma$在该值上的值。
如果$\sigma(i) \neq i$，我们说$\sigma$移动$i$，如果$\sigma(i)=i$，我们说$\sigma$固定$i$。$\sigma$的支持集$\operatorname{Supp} \sigma$是集合
即由$\sigma$移动的$\{1, \ldots, n\}$的子集。因此$\operatorname{Supp} \sigma=\emptyset \Longleftrightarrow \sigma=1$。
$S_{n}$有许多有趣的子群。例如，子集$H_{n}$定义为
很容易验证它是同构于$S_{n-1}$的$S_{n}$的子群。事实上，对于所有的$i$，我们可以定义$H_{i}=\left\{\sigma \in S_{n}: \sigma(i)=i\right\}$。它也同构于$S_{n-1}$，因为它可以被视为集合$X=\{1, \ldots, n\}-\{i\}$的排列集合，该集合有$n-1$个元素。如果$n=n_{1}+n_{2}$对于两个正整数$n_{1}, n_{2}$，那么子集
也是$S_{n}$的子群。请注意，如果$\sigma \in H_{n_{1}, n_{2}}$，那么自动地
事实上，很容易验证$H_{n_{1}, n_{2}}$同构于$S_{n_{1}} \times S_{n_{2}}$。$S_{n}$还有许多其他子群。例如，如果$\sigma \in S_{n}$定义为$\sigma(i)=i+1$对于$i \leq n-1$，并且$\sigma(n)=1$，那么很容易验证$\sigma$的阶是$n$，因此$\langle\sigma\rangle$是同构于$\mathbb{Z} / n \mathbb{Z}$的$S_{n}$的子群。二面体群$D_{n}$，即平面中正$n$边形的对称群，通过观察n边形顶点的排列，同构于$S_{n}$的一个子群。注意$\#\left(D_{n}\right)=2 n$，因此如果$n \geq 4$，则$D_{n}$是$S_{n}$的真子群。我们将看到（凯莱定理），如果$G$是有限群，那么存在一个$n$使得$G$同构于$S_{n}$的一个子群（事实上可以取$n=\#(G)$）。因此群$S_{n}$非常复杂，因为它们包含所有可能的有限群，直到同构作为子群。
要描述函数$\sigma:\{1, \ldots, n\} \rightarrow\{1, \ldots, n\}$，不一定是排列，我们可以给出其值的表格，记录$i$然后$\sigma(i)$，如下所示：
| $i$ | 1 | 2 | $\ldots$ | $n$ |
|---|---|---|---|---|
| $\sigma(i)$ | $\sigma(1)$ | $\sigma(2)$ | $\ldots$ | $\sigma(n)$ |
当然，我们可以用一个$2 \times n$矩阵来描述相同的信息：
那么$\sigma$是排列的条件就是整数$1, \ldots, n$在矩阵的第二行中每个恰好出现一次。当然，第一行是冗余的，$\sigma$可以